package lq1390;

import java.util.LinkedList;
import java.util.Scanner;

//蓝桥杯官网题库1390，已AC
/*
测试数据
3
0 10 
5 15 
10 15 
2 
0 10 
10 20 
0

*/
public class Main {

	//飞机数量区间[2,8]
	static int maxn = 10;
	//飞机实例数组
	static Plane[] s= new Plane[maxn];
	//全排列情况，链表保存
	static LinkedList<int[]> p = new LinkedList<int[]>();
	//当前飞机数量
	static int n = 3;
	//当前情况最优解
	static double ans;
	//全部情况计数
	static int count = 0;
	public static void main(String[] args) {
		
		//输入处理
		Scanner sc=new Scanner(System.in);
		n = sc.nextInt();
		while(n!=0) {  //输入0退出循环
			count++;   //Case计数
			//获取当前情况的数据
			//s从下标1开始记录
			for(int i=1;i<=n;i++) {
				s[i] = new Plane(sc.nextInt(),sc.nextInt(),i);
			}
			
			//输出检查数据获取情况
			/*
			for(int i=1;i<=n;i++) {
				System.out.println(s[i]);
			}
			*/
			
			//根据飞机数量全排列，链表保存，输出结果
			p.clear();//清空链表
			dfs(0,n);
			//显示全排列情况
			/*
			while(!p.isEmpty()) {
				int[] temp = p.pollFirst();
				for(int i=0;i<n;i++) {
					System.out.print(temp[i]);
				}
				System.out.println();
			}
			*/
			
			//初始化ans
			ans = 0;
			//遍历全部降落情况
			while(!p.isEmpty()) {
				//获取一种降落情况
				int[] temp = p.pollFirst();
				//二分查找最优解
				//题目给出的最大区间
				double l=0,r=1440,mid;
				//二分缩小区间，找到解mid
				//下面是实数二分模板代码
				while(r-l>1e-6)//二分查找最优解 
				{
					mid=(l+r)/2;
					if(check(mid,temp)==1)//当前的间隔满足条件 
						l=mid;
					else//当前间隔太长 
						r=mid; 
				} 
				//维护符合要求最大区间 
				//全部降落情况所有解中找最大的
				ans=Math.max(ans,r);
				
			}
			//格式化输出答案
			//分钟数直接取整数部分
			int m = (int)Math.floor(ans);
			//秒数部分减掉分钟数再乘60后四舍五入
			int s = (int)Math.round((ans-m)*60);
			//格式化输出
			if(s<10)
				System.out.printf("Case %d: %d:0%d\n",count,m,s);
			else{
				System.out.printf("Case %d: %d:%d\n",count,m,s);
			}
			
			//获取下一轮飞机数量
			n = sc.nextInt();
		}
		
	}
	
	//二分check
	//按题意要求舍入到最近的分和秒，所以选择实数二分做法
	//mid:二分测试的值
	//sx：飞机降落的顺序
	//根据间隔时间mid和降落顺序sx模拟降落的情况，检查是否每个飞机都在时间区间内
	static int check(double mid,int[] sx)
	{
		//第一架降落飞机的最早降落点
		double x=s[sx[0]].L;
		
		//从第二架降落飞机开始判断 
		for(int i=1;i<n;i++)
		{
			//与上一架飞机间隔mid降落 
			x+=mid;
			//当前间隔超出当前飞机的降落区间（间隔太长了）
			if(x>s[sx[i]].R) 
				return 0;
			//当前间隔小于当前飞机降落区间（间隔太短了） 
			if(x<s[sx[i]].L)
				x=s[sx[i]].L;//直接让当前飞机在自己最早降落时间降落
			
			//两个if都判定失败，即在当前飞机区间内降落，继续判断下一架飞机 
		} 
		return 1; //所有飞机降落符合要求，当前间隔是可行解 
	}
	
	
	//全排列部分
	//20个下标待排列
	static int[] a = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
	//保存每次全排列的结果
	static int[] b = new int[20];
	//记录每个位置的下标是否用过
	static boolean[] vis = new boolean[20];
	//dfs从小到大输出排列
	//s:排列开始位置
	//t:排列结束位置
	static void dfs(int s,int t){
		if(s==t) {
			//找到一个全排列情况
			//链表保存排列结果
			int[] temp = new int[n];
			for(int i=0;i<t;i++) {
				temp[i] = b[i];
			}
			p.add(temp);
			return;
		}
		for(int i=0;i<t;i++) {
			//找未使用的下标，设为使用，然后开始dfs
			if(!vis[i]) {
				vis[i] = true;
				b[s] = a[i];
				dfs(s+1,t);
				//回溯，退回时vis[i]复原
				vis[i] = false;
			}
		}
	}

}
class Plane{
	int L; //降落时间区间左边界
	int R; //降落时间区间右边界
	int id; //飞机编号
	public Plane(int l, int r, int id) {
		this.L = l;
		this.R = r;
		this.id = id;
	}
	@Override
	public String toString() {
		return "Plane [L=" + L + ", R=" + R + ", id=" + id + "]";
	}
	
}



